#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <list>

using namespace std;

// 链式hash表
// 虽然也会产生hash冲突，但是由于是把链表插入到对应hash桶中，所以相对线性探测hash来说效率更高
// 多线程场景下，可以只对当前桶加锁，效率更高

class LinkHashTable
{
public:
    LinkHashTable(int size = primes_arr[0],float hashFactor = 0.75)
                    :primeIdx_(0)
                    ,bucketusednum_(0)
                    ,hashFactor_(hashFactor)
    {
        if (size != primeIdx_)
        {
            for (; primeIdx_ < PRIME_NUM; primeIdx_++)
            {
                if (primes_arr[primeIdx_]>= size)
                {
                    break;
                }
            }

            if (primeIdx_ == PRIME_NUM)
            {
                throw "error: the size is too large, can't expand the hash tabel.";
            }
        }
        
        // 初始化table_
        table_.resize(primes_arr[primeIdx_]);
    }

    ~LinkHashTable()
    {

    }

    void insert(int key)
    {
        float loadFactor = bucketusednum_ * 1.0 / table_.size();
        cout << "key:" <<  key <<" loadFactor : " << loadFactor << endl;
        // 装载因子大于0.75，扩容
        if (loadFactor >= hashFactor_)
        {
            // 扩容
            resize();
        }

        // 计算索引值
        int index = hashcalc(key);
        cout << "index : " << index << endl;
        // 插入
        // 先判断桶是否为空，如果为空，直接插入
        if (table_[index].empty())
        {
            // 由于emplacefront避免了临时对象的创建和拷贝 / 移动操作，在构造复杂对象时，
            // 相比pushback能显著提高性能 ，减少不必要的开销。不过在简单对象（如内置类型）的插入中，
            // 两者的性能差异可能并不明显。
            table_[index].emplace_front(key);
            cout << key << " insert success" << endl;
            bucketusednum_++;
        }
        // 如果桶不为空，判断key是否已经存在，如果不存在，判断去重后插入到链表头部
        else
        {
            // 去重
            // 因为本身需要实现find，所以此处用 ::find 表示使用泛型算法的函数
            auto it = ::find(table_[index].begin(), table_[index].end(), key);
            if (it == table_[index].end())
            {
                table_[index].emplace_front(key);
                cout << key << " insert success" << endl;
                bucketusednum_++;
            }
        }
    }

    void remove(int key)
    {
        // 计算索引值
        int index = hashcalc(key);
        // 删除
        // 先判断桶是否为空，如果为空，直接返回
        if (table_[index].empty())
        {
            return;
        }
        // 如果桶不为空，则直接查找元素
        else
        {
            // 查找
            auto it = ::find(table_[index].begin(), table_[index].end(), key);
            if (it != table_[index].end())
            {
                table_[index].erase(it);
                if (table_[index].empty())
                {
                    bucketusednum_--;
                }
            }
        }
    }

    bool find(int key)
    {
        int index = hashcalc(key);
        // 先判断桶是否为空，如果为空，直接返回
        // 如果桶不为空，判断key是否已经存在，如果存在，删除
        if (table_[index].empty())
        {
            return false;
        }
        else
        {
            // 查找
            auto it = ::find(table_[index].begin(), table_[index].end(), key);
            return it != table_[index].end();
        }
    }

private:
    // 计算hash值
    int hashcalc(int key)
    {
        return key % table_.size();
    }

    void resize()
    {
        if (primeIdx_ == PRIME_NUM)
            throw "error: the size is too large, can't expand the hash tabel.";

        cout << "old table size to " << table_.size() << endl;
        // 扩容
        vector<list <int>> temptable;
        // 将 table_ 中的元素拷贝到 temptable 中，并将table_清空
        table_.swap(temptable);
        table_.resize(primes_arr[++primeIdx_]);
        // 重新计算哈希桶的使用个数，因为链式hash表中，重新构造时
        // 映射关系会发生改变
        bucketusednum_ = 0;

        for (auto item_list : temptable)
        {
            for (auto item : item_list)
            {
                int index = hashcalc(item);
                table_[index].emplace_front(item);
                bucketusednum_++;
            }
        }
    }
private:
    // hash桶的成员是链表，链表中的节点是int类型
    // 桶的长度 直接使用 table_.size()
    vector<list <int>> table_;
    // 已使用的桶的个数
    int bucketusednum_;
    // hash因子
    float hashFactor_;
    // 哈希表质数索引
    int primeIdx_;
    // 哈希表质数个数
    static const int PRIME_NUM = 28;
    // 哈希表质数表
    static long long primes_arr[PRIME_NUM]; // 哈希表质数表
};

// 如果质数表初始化为3的时候会出现问题，因为2 / 3 会一直小于默认的0.75，导致hash表不会扩容
// 从而使得hash桶的链表无限增长，导致查找效率劣化
// 可以通过控制链表长度等方法来改善，此处直接排除掉质数3
long long LinkHashTable::primes_arr[PRIME_NUM] = {7, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 
                                         49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 
                                         6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 
                                         402653189, 805306457, 1610612741, 3221225473};



int main()
{
    LinkHashTable table;
    table.insert(1);
    table.insert(2);
    table.insert(10);
    table.insert(8);

    int n = table.find(10);
    cout << "n : " << n << endl;
    table.remove(10);
    n = table.find(10);
    cout << "n : " << n << endl;
    return 0;
}
